[Algorithm] 시리즈는 제가 알고리즘 공부를 하면서 정리한 글들을 모은 시리즈입니다.
제가 공부하고 정리한 내용이 부족할 수 있습니다. 댓글로 도움을 주신다면 감사하겠습니다.

버블 정렬(Bubble Sort)

버블 정렬은 정렬 알고리즘 중 하나입니다. 배열에서 비교 연산 실행 시 큰 값을 오른쪽으로 보내며, 가장 작은 값이 배열의 가장 처음 요소에 위치할 때까지 반복합니다.

위 내용을 이해하기 위해 첫 번째 패스의 동작 과정을 알아봅시다. 여기서 패스란 알고리즘의 한 번의 반복 과정입니다.

첫 번째 패스의 동작 과정

아래와 같은 배열이 있다고 가정하겠습니다.

[12, 3, 5, 9, 7]

해당 배열을 버블 정렬을 사용하여 정렬을 시도할 때, 첫 번째 패스의 과정은 아래와 같습니다.
소괄호는 과정마다 비교되는 요소들을 나타냅니다.

첫 번째 요소와 인접한 두번째 요소를 비교한 뒤, 큰 값을 뒤로 보냅니다.

[(12, 9), 5, 9, 7] -> [9, 12, 5, 9, 7]

두 번째 요소와 인접한 세 번째 요소를 비교한 뒤, 큰 값을 뒤로 보냅니다.

[3, (12, 5), 9, 7] -> [3, 5, 12, 9, 7]

세 번째 요소와 인접한 네 번째 요소를 비교한 뒤, 큰 값을 뒤로 보냅니다.

[3, 5, (12, 9), 7] -> [3, 5, 9, 12, 7]

네 번째 요소와 인접한 마지막 요소를 비교한 뒤, 큰 값을 뒤로 보냅니다.

[3, 5, 9, (12, 7)] -> [3, 5, 9, 7, 12]

따라서 첫 번째 패스 이후 배열의 정렬 상태는 아래와 같습니다.

[9, 3, 5, 12, 7] -> [3, 5, 9, 7, 12]

첫 번째 패스의 동작 과정처럼 한 단계식 값이 bubble up 한다고 하여 Bubble Sort라는 이름이 붙여졌습니다.

이를 통해 버블 정렬의 동작과정을 정리하자면 아래와 같습니다.

알고리즘의 동작 과정

패스가 반복될 때마다 배열의 오른쪽 부분은 정렬된 상태입니다. 즉, 제일 큰 값인 12가 제일 뒤에 위치하게 된 것 처럼 첫 번째 패스에서 한 개의 요소가 올바른 위치에 있는 것이 보장됩니다. 이 이유는 인접한 두 요소를 비교한 뒤 큰 값을 오른쪽으로 스왑하기 때문입니다. 결국에는 패스마다 요소가 한 개씩 올바른 위치에 정렬됩니다.

이것이 의미하는 것은 패스가 반복될 수록 배열의 오른쪽 부분은 정렬된 상태가 되는 것이 보장되고, 나머지는 아직 정렬되지 않은 상태가 될 수 있다는 것입니다.(배열의 초기상태에 의해 정해집니다.) 또한, 패스마다 비교해야할 부분은 배열의 정렬되지 않은 부분이기 때문에 비교해야 할 요소의 개수가 줄어든다는 얘기입니다. 따라서 동작 과정은 아래와 같습니다.

첫 번째 요소부터 시작해서 인접한 두개의 요소를 비교합니다.

비교한 두 값 중 큰 값이 오른쪽으로 갈 수 있도록 두 요소의 자리를 스왑합니다.

1, 2의 과정을 배열의 정렬되지 않은 부분에서 계속 반복합니다.

버블 정렬의 구현

이제 동작 과정에 대해 알았으니 직접 코드로 버블 정렬을 구현해봅시다.
직접 코드로 버블 정렬을 구현할 때 필요한 내용은 다음과 같습니다.

정렬할 배열

버블 정렬의 패스를 반복할 반복문. 패스는 총 \(n-1\)번 반복합니다.(요소 5개를 정렬하기 위해서는 4번의 반복이 필요합니다.)

패스마다 배열의 정렬되지 않은 부분의 비교를 수행할 반복문. 패스의 반복에 따라 비교를 수행할 반복 횟수가 정해집니다.

구현할 때 사용할 언어는 Java입니다.

버블 정렬 구현 코드

Class BubbleSort {
    public static void main(String[] args) {
        int[] array = {12, 3, 5, 9, 7};
        int n = array.length;

        // 2에 해당하는 반복문
        for(int i = 0; i < n-1; i++) {
            // 3에 해당하는 반복문
            for(int j = 0; j < n-i-1; j++) {
                if(array[j] > array[j+1]) { // 비교 연산의 부분
                    // swap 연산의 부분
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }

        for (int a: array) {
            System.out.print(a + " ");
        }
    }
}

이런식으로 해당 알고리즘의 동작 방식에 맞춰서 구현할 수 있습니다. 하지만 이런식으로 구현한 버블 정렬에는 한가지 개선할 수 있는 사항이 있습니다.

향상된 버블 정렬

아래와 같은 배열을 버블 정렬을 사용해서 정렬하겠다고 해보겠습니다.

[5, 3, 7, 9, 13]

해당 배열을 버블 정렬을 통해 정렬하게 될 경우 첫 번째 패스의 첫 번째 비교 & 스왑 연산에 의해 정렬이 완료됩니다.

[(5, 3), 7, 9, 13] -> [3, 5, 7, 9, 13]

모든 요소가 올바르게 정렬 되었기 때문에 스왑 연산은 수행되지 않지만 비교 연산은 계속해서 수행됩니다.

[3, (5, 7), 9, 13] -> [3, 5, 7, 9, 13]

[3, 5, (7, 9), 13] -> [3, 5, 7, 9, 13]

[3, 5, 7, (9, 13)] -> [3, 5, 7, 9, 13]

즉, 우리는 불필요한 비교 연산을 제거한다면 더 효율적인 버블 정렬을 사용할 수 있습니다.
기본적인 틀은 위에서 구현한 버블 정렬과 동일합니다. 개선하기 위해서는 한 가지 조건만 추가하면 됩니다.

스왑이 일어나지 않았다면 반복문을 종료

비교 연산 수행 중 아무런 스왑도 일어나지 않았다면 해당 배열은 이미 정렬이 완료된 상태임을 보장할 수 있습니다. 코드로 구현하자면 아래와 같습니다.

Class BubbleSort {
    public static void main(String[] args) {
        int[] array = {12, 3, 5, 9, 7};
        int n = array.length;

        // 2에 해당하는 반복문
        for(int i = 0; i < n-1; i++) {
            //비교 & 스왑 연산에 들어가기 전에 false로 초기화
            boolean swapped = false;

            // 3에 해당하는 반복문
            for(int j = 0; j < n-i-1; j++) {
                if(array[j] > array[j+1]) { // 비교 연산의 부분
                    // swap 연산의 부분
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    swapped = true; // 스왑 연산이 일어났다면 true로 변경
                }
            }

            // 비교 & 스왑연산을 거쳤는데 스왑이 일어나지 않았다면 반복문 종료
            if(!swapped) {
                break;
            }
        }

        for (int a: array) {
            System.out.print(a + " ");
        }
    }
}

버블 정렬의 시간복잡도

점근적 표기법

알고리즘의 시간복잡도는 점근적 표기법을 사용해서 나타냅니다. 점근적 표기법에는 Big-θ(빅 세타 표기법), Big-O(빅 오 표기법), Big-Ω (빅 오메가 표기법) 이렇게 세 가지가 있습니다. 여기에서는 Big-O(빅 오 표기법)을 사용해서 표현하겠습니다.

간단하게 설명 드리자면, 알고리즘의 성능을 측정할 때는 입력값을 모두 처리하기까지 알고리즘이 연산을 몇 번 수행했는지가 아니라, 얼마나 걸렸는지를 기준으로 측정합니다. 즉, 얼마나 걸렸는지는 알고리즘의 실행 시간이 됩니다.

알고리즘의 실행시간은 총 두 가지 방법으로 나타낼 수 있습니다. 첫 번째는 입력값 \(n\)에 대한 다항식을 세워서 실제 시간을 계산할 수 있습니다. 두 번째는 입력값 \(n\)의 크기에 따라 실행시간의 성장률로 나타낼 수 있습니다.(\(n\)에 관한 다항식에서 가장 큰 차수만 고려하는 것입니다.) 여기서 두 번째 방법이 바로 점근적 표기법에 해당합니다.

위 내용에 대한 더 자세한 내용은 여기에서 확인하세요!(참고자료)

Big-O(빅 오 표기법)를 사용하는 이유는 점근적 한계를 위에만 두기 때문입니다. Big-θ(빅 세타 표기법)의 경우 위아래에 점근적으로 근접한 한계가 있습니다. 알고리즘의 실행시간을 나타낼 때 Big-θ(빅 세타 표기법)로 나타내면 해당 실행시간의 범위를 알아낼 수 있습니다. 하지만, 모든 경우에 적용되는 것이 아니기 때문에 표현할 때 실행시간이 최대 얼만큼 걸릴 수 있다는 것을 나타내기 위해 Big-O(빅 오 표기법)을 사용합니다.

위 내용에 대한 더 자세한 내용은 여기에서 확인하세요!(참고자료)

그래서 버블 정렬의 시간복잡도는?

점근적 표기법에 대한 설명은 이쯤하고, 다시 버블 정렬의 시간복잡도로 넘어와보겠습니다.
이제 점근적 표기법을 사용하여 버블 정렬의 시간복잡도를 나타내보겠습니다.
평균의 경우 스왑 연산의 경우 정렬된 배열의 초기 상태에 따라 다르기 때문에 일반식을 세우기가 어렵습니다. 따라서 비교하고 스왑의 대상이 되는 대상 요소의 개수로 식을 세우겠습니다. 패스당 비교 되고 스왑의 대상이 되는 요소의 개수는 \(\frac {n}{2}\)개 입니다. 이는 아래의 식으로 확인해 볼 수 있습니다.

첫 번째 패스
\(n-1\)개의 요소를 비교 및 스왑이 발생할 수 있다.
두 번째 패스
\(n-2\)개의 요소를 비교 및 스왑이 발생할 수 있다.
세 번째 패스
\(n-3\)개의 요소를 비교 및 스왑이 발생할 수 있다. \(…\)

따라서 식을 세워보면 아래와 같습니다.

\[Operations = (n-1) + (n-2) + … + 2 + 1 \]

\( (n-1) + (n-2) + … + 2 + 1 \)의 합을 \(S\)로 놓으면 아래와 같이 나타낼 수 있습니다.

아래의 두 식을 더하면

\[S = 1 + 2 + 3 + … + (n-2) + (n-1)\] \[ +\] \[S = (n-1) + (n-2) + (n-3) + … + 2 + 1\]
\[2S = \underbrace{n + n + … + n}_{\text{n-1개}}\]

\[\therefore S = \frac {n(n-1)}{2} \]
따라서 버블 정렬의 연산 횟수, Operations는 아래와 같습니다.

\[Operations = \frac {n(n-1)}{2}\]
\[Operations = \frac {n^2}{2} - \frac {n}{2}\]
이를 Big-O(빅 오 표기법)으로 나타낸다면 아래와 같습니다.

\[ Operations = O(n^2)\]
따라서 버블 정렬의 시간 복잡도는 \(O(n^2)\)입니다.

변수의 초기화